import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;


public class DFA {
	HashMap<Character, Integer>[] table;
	boolean[] isAccept;
	int start, cur;
	String[] tokens;
	
	/**
	 * Constructor to build a DFA from an NFA using subset construction
	 * @param n the NFA to generate the DFA from
	 */
	@SuppressWarnings("unchecked")
	public DFA(NFA n, HashMap<String, Integer> pmap) {
		Set<State> cur = n.getStart().epsilonClosure();
		HashMap<Set<State>, HashMap<Character, Set<State>>> dfaTable = new HashMap<Set<State>, HashMap<Character, Set<State>>>();
		LinkedList<Set<State>> queue = new LinkedList<Set<State>>();
		queue.add(cur);
		HashMap<Character, Set<State>> transitions;
		Set<State> curStates;
		while(!queue.isEmpty()) {
			cur = queue.remove();
			if(!dfaTable.containsKey(cur)) {
				transitions = new HashMap<Character, Set<State>>();
				dfaTable.put(cur, transitions);
				for(State s : cur) { //For every state,
					for(Character c : s.getTransitions().keySet()) { //For every character transition from that state,
						
						curStates = transitions.get(c);
						if(curStates == null) {
							curStates = new HashSet<State>();
							transitions.put(c, curStates);
						}
						//Create the new superstate by adding the epsilon closure 
						for(State state : s.transition(c))
							curStates.addAll(state.epsilonClosure());
					}
				}
				
				for(Set<State> states : transitions.values()) {
					if(!dfaTable.containsKey(states)) {
						queue.add(states);
					}
				}
			}
		}
		
		
		table = new HashMap[dfaTable.size()];
		isAccept = new boolean[dfaTable.size()];
		tokens = new String[dfaTable.size()];
		HashMap<Set<State>, Integer> reduceMap = new HashMap<Set<State>, Integer>();
		int i = 0;
		String token = "";
		
		for(Set<State> states : dfaTable.keySet()) {
			int priority = Integer.MAX_VALUE;
			for(State state : states) {
				if(state.isAccept()) {
					isAccept[i] = true;
					if(priority > pmap.get(state.getToken())) {
						token = state.getToken();
						priority = pmap.get(state.getToken());
					}
				}
			}
			table[i] = new HashMap<Character, Integer>();
			tokens[i] = token;
			token = "";
			reduceMap.put(states, i++);
		}
		i = 0;
		for(Set<State> states : dfaTable.keySet()) {
			for(Map.Entry<Character, Set<State>> c : dfaTable.get(states).entrySet()) {
				table[i].put(c.getKey(), reduceMap.get(c.getValue()));
			}
			if(n.getStart().epsilonClosure().equals(states))
				start = i;
			i++;
		}
		i = 0;
	}
	
	
	
	/**
	 * Given a scanner, run its contents through the DFA and generate tokens.
	 * @param s the scanner
	 */
	public Token[] tokenize(Scanner s) {
		String cur, lastAcceptToken = "";
		int i, j, tableInd, lastAccept = -1;
		int count = 0;
		ArrayList<Token> list = new ArrayList<Token>();
		while(s.hasNextLine()) {
			cur = s.nextLine();
			i = 0;
			j = 0;
			tableInd = start;
			lastAcceptToken = "";
			lastAccept = -1;
			while(i < cur.length()) {
				count++;
				if(table[tableInd].get(cur.charAt(i)) == null) {  //We failed, see what we should do.
					if(!tokens[tableInd].isEmpty()) 
						list.add(new Token(tokens[tableInd].substring(1), cur.substring(j, i)));
						//System.out.println(tokens[tableInd].substring(1) + " " + cur.substring(j, i));
					else if(lastAccept != -1) { //Roll back
						i = lastAccept + 1;
						list.add(new Token(lastAcceptToken.substring(1), cur.substring(j, i-1)));
						//System.out.println(lastAcceptToken.substring(1) + " " + cur.substring(j, i));
					}
					if(tableInd == start)
						i++;
					j = i;
					tableInd = start;
					lastAcceptToken = "";
					lastAccept = -1;
				} else {
					tableInd = table[tableInd].get(cur.charAt(i++));
					if(!tokens[tableInd].isEmpty()) {
						lastAcceptToken = tokens[tableInd];
						lastAccept = i;
					}
				}
			}
			if(!tokens[tableInd].isEmpty()) {
				list.add(new Token(tokens[tableInd].substring(1), cur.substring(j, i)));
				//System.out.println(tokens[tableInd].substring(1) + " " + cur.substring(j, i));
			} else if(lastAcceptToken != "") {
				list.add(new Token(lastAcceptToken, cur.substring(j, lastAccept)));
			}
			
		}
		//System.out.println("Number of transitions: " + count);
		return list.toArray(new Token[list.size()]);
	}

}
